1. Field of the Invention
The present invention relates to a system and method for routing data packets in a wireless communication network, in particular, an ad-hoc peer-to-peer multi-hopping wireless communication network, using tree dependency and time division multiple access methods. More particularly, the present invention relates to a system and method for using tree dependency and time division multiple access methods to route packets in a wireless ad-hoc peer-to-peer multi-hopping wireless communication network based on the type or class of data packets while minimizing overhead and delay and improving communication reliability.
2. Description of the Related Art
In recent years, a type of mobile communications network known as an “ad-hoc” network has been developed. In this type of network, each mobile node is capable of operating as a base station or router for the other mobile nodes, thus eliminating the need for a fixed infrastructure of base stations. As can be appreciated by one skilled in the art, network nodes transmit and receive data packet communications in a multiplexed format, such as time-division multiple access (TDMA) format, code-division multiple access (CDMA) format, or frequency-division multiple access (FDMA) format.
More sophisticated ad-hoc networks are also being developed which, in addition to enabling mobile nodes to communicate with each other as in a conventional ad-hoc network, further enable the mobile nodes to access a fixed network and thus communicate with nodes of other networks, such as those on the public switched telephone network (PSTN) and on other networks such as the Internet. Details of these advanced types of ad-hoc networks are described in U.S. Pat. No. 7,072,650 entitled “Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks”, issued on Jul. 4, 2006, in U.S. Pat. No. 6,807,165 entitled “Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel”, and in U.S. Pat. No. 6,873,839 entitled “Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System”, issued on Mar. 29, 2005, the entire content of each being incorporated herein by reference.
As can be appreciated by one skilled in the art, ad-hoc multihopping networks must provide services for transporting various classes of data. Each class has its own requirements regarding the pipeline delay, jitters and integrity. Voice data are transported in network as very frequent short packets that must be delivered with very little delay. Voice packets that become very late can be dropped if such action does not affect too much the quality of sound. The stream of voice data “flows” in the network for several minutes.
Data transfer between computers (file transfer) is executed in large packets. These packets could be delivered with very large delays and jitters. The integrity of data transferred between computers is essential. Depending on the size of the data file, the transport of data over the wireless network takes, from less than one second to several seconds. Multimedia data (real time video and sound) are not restricted on pipeline delay, but require integrity of data, low jitter and synchronization of clocks at both ends of the link, in case the communication continues for long time. Multimedia data flows in network from several minutes to tens of minutes.
The class of data is used for differential handling of packets while transferred in the wireless network in order to comply with the requirements of each class. Emergency requests have higher scheduling priority than any other class of data.
Many schemes have been proposed in the literature for routing data packets using TDMA. For example, U.S. Pat. No. 6,807,165 relates to a time division protocol for an ad-hoc, peer-to-peer radio network having coordinating channel access to shared parallel data channels with separate reservation channel. Moreover, U.S. Pat. No. 6,594,273 relates to a TDMA protocol for use with wireless multihopping networks. U.S. Patent Application No. 20030185166, entitled, “Time division protocol for an AD-HOC, peer-to-peer radio network having coordinating channel access to shared parallel data channels with separate reservation channel”, U.S. Patent Application No. 20030227895, “System and method for improving the accuracy of time of arrival measurements in a wireless ad-hoc communications network”, and U.S. Patent Application No. 20040005902, entitled “System and method for correcting the clock drift and maintaining the synchronization of low quality clocks in wireless networks” discuss routing methods using TDMA. Moreover, systems and methods for routing data packets are discussed in the following references: Broch et al., “A Performance Comparison of Multi-Hop Ad Hoc Network Routing Protocols”, Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking; Young, “USAP: A Unified Dynamic Distributed Multichannel TDMA Slot Assignment Protocol”; Elliot et al., “Self-organizing, self-healing wireless networks IEEE”; Garcia-Luna-Aceves et al., “Reversing the collision-avoidance handshake in wireless networks”; Garcia-Luna-Aceves et al., “Transmission-Efficient Routing in Wireless Networks Using Link-State Information”; Garcia-Luna-Aceves et al., “The Core-Assisted Mesh Protocol”, IEEE Journal On Selected Areas In Communications: Vol. 17, No. 8 (1999); ISO/IEC 8802-11 ANSI/IEEE Std 802.11. First edition 1999-00-00; Kamerman et al., “Net Throughput with IEEE 802.11 Wireless Lans”, WCNC (2000); McChesney, “SUO Phase I Channel access protocol”; McChesney et al., “Optimization of an Adaptive Link Control Protocol for Multimedia Packet Radio Networks”; Ramanathan et al., “Topology control of multihop wireless networks using transmit power adjustment”; Ramanathan et al., “Hierarchically-organized, multihop mobile wireless networks for quality-of-service support”; Steenstrup, “Dynamic Multipoint Virtual Circuits for Multimedia traffic in Multihop Mobile Wireless Networks”; Tang et al., “Collision-avoidance transmission scheduling for ad-hoc networks”; Vardacas et al., “QoS Networking with Adaptive Link Control and Tactical Multi-Channel software radios”. The entire contents of all patents, patent applications, and reference cited herein are incorporate by reference.
A need remains, however, for a method for routing data packets in an ad-hoc multihopping network in a manner such that efficient utilization of channel bandwidth occurs.